'''
将两个升序链表合并为一个新的升序链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成
示例：
输入：1->2->4,1->3->4
输出：1->1->2->3->4->4
'''

#定义链表节点
class ListNode():
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

#合并两个链表
def mergeTwoLists(l1:ListNode, l2:ListNode)-> ListNode:
    #创建一个哨兵节点，从而简化节点为空等边界条件
    dumpy = ListNode(0)
    # current指向已合并链表的最后一个节点
    current = dumpy

    #比较两个链表的节点，将current指向较小的节点
    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        #移动current到合并后链表的下一位置
        current = current.next
    #如果链表非空，则将剩余的链表直接接到后边
    if l1:
        current.next = l1
    else:
        current.next = l2
    #返回拼接后的链表
    return dumpy.next

#示例
l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(4)

l2 = ListNode(1)
l2.next = ListNode(3)
l2.next.next = ListNode(4)

l3 = mergeTwoLists(l1, l2)
current = l3
while current:
    print(current.val,end='->')
    current = current.next

